
class T {
public:
    bool operator()(pair<int, int>& p1, pair<int, int>& p2) {
        return p1.second > p2.second;
    }
};
class Solution {
public:
    long long maxSpending(vector<vector<int>>& values) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, T> pq;
        long long ans = 0,d = 1;
        int m = values.size(), n = values[0].size();
        vector<int> pos(m, n - 2);
        for (int i = 0; i < m; i++) {
            pq.push({i, values[i][n - 1]});
        }
        while (!pq.empty()) {
            auto t = pq.top();
            pq.pop();
            ans += d++ * (t.second);
            //cout << ans << ' ';
            int a = t.first;
            if (pos[a] >= 0) {
                pq.push({a, values[a][pos[a]]});
                pos[a]--;
            }
        }
        return ans;
    }
};